# -*- coding: utf-8 -*-
import re
import fractions
import operator
import types

############
#
# Scheme types
#
#
class List(object):

    def __init__(self, car=None, cdr=None):
        if type(car) == list:
            if len(car) == 0:
                self.car = None
                self.cdr = None
            elif len(car) == 1:
                self.car = car[0]
                self.cdr = None
            else:
                self.car = car[0]
                self.cdr = List(car[1:])
        else:
            self.car = car
            self.cdr = cdr

    def __len__(self):
        if self.car == None:
            return 0
        i = 1
        lst = self
        while lst.cdr != None:
            if type(lst.cdr) != List:
                raise SchemeError('Wrong argument type')
            lst = lst.cdr
            i += 1
        return i

    def __getitem__(self, key):
        if type(key) != int:
            raise TypeError()
        if key < 0:
            raise SchemeError('Index ' + str(key) + ' not found in list.')
        if key >= len(self):
            raise IndexError()
        lst = self
        try:
            for i in xrange(0, key):
                lst = lst.cdr
            return lst.car
        except AttributeError:
            raise SchemeError('Index ' + str(key) + ' not found in list.')

    def __setitem__(self, key, value):
        if type(key) != int:
            raise TypeError()
        if key < 0:
            raise SchemeError('Index ' + str(key) + ' not found in list.')
        lst = self
        try:
            for i in xrange(0, key):
                lst = lst.cdr
            lst.car = value
        except AttributeError:
            raise SchemeError('Index ' + str(key) + ' not found in list.')

    def append(self, value):
        if self.car == None:
            self.car = value
            return
        lst = self
        while lst.cdr != None:
            if type(lst.cdr) != List:
                raise SchemeError('Wrong argument type')
            lst = lst.cdr
        lst.cdr = List(value, None)

    def _str(self):
        if type(self.cdr) == List:
            return str(self.car) + ' ' + self.cdr._str()
        elif self.cdr == None:
            if self.car == None:
                return ''
            else:
                return str(self.car)
        else:
            return str(self.car) + ' . ' + str(self.cdr)

    def __str__(self):
        return '(' + self._str() + ')'

    def __repr__(self):
        return str(self)

    def __iter__(self):
        l = []
        if self.car == None:
            return l
        lst = self
        while lst != None:
            if type(lst.cdr) != List and lst.cdr != None:
                raise SchemeError('Wrong argument type')
            l.append(lst.car)
            lst = lst.cdr
        return l.__iter__()

    def __eq__(self, obj):
        if type(obj) != List:
            return False
        return self.car == obj.car and self.cdr == obj.cdr

    def tuple(self):
        return (self.car, self.cdr)


class Vector(list):

    def __init__(self, data=[]):
        self.closed = False
        for d in data:
            self.append(d)
        if data != []:
            self.closed = True

    def append(self, value):
        if self.closed:
            raise SchemeError('Can\'t append to vectors!')
        else:
            list.append(self, value)

    def close(self):
        self.closed = True

    def __str__(self):
        s = '#('
        for item in self:
            s += str(item) + ' '
        return s[:-1] + ')'

    def __repr__(self):
        return str(self)


class Datum(str):

    def __str__(self):
        return '(quote ' + self + ')'

    def __hash__(self):
        return self.value.__hash__()


class Procedure(object):

    def __init__(self, parameters, body, env):
        self.parameters = parameters
        self.body = body
        self.env = env

    def __str__(self):
        return '#<procedure>'


class Primitive(object):

    """
    The validation parameter can receive these values:
      * None: no validation will be made.
      * One function: free number of parameters, all will be validated
        according to this function.
      * A tuple of functions: the parameters will be validates against
        the functions in the tuple. The number of parameters must match
        the number of validations in the tuple.
    """
    def __init__(self, proc, validation=None):
        self.proc = proc
        self.validation = validation

    def apply(self, args):
        # Validate arguments
        if type(args) != list:
            raise TypeError('Invalid validation parameter.')
        if self.validation == None:
            pass
        elif type(self.validation) == types.FunctionType:
            for a in args:
                if not self.validation(a):
                    raise SchemeError('Invalid argument type ' + str(a))
        elif type(self.validation) == tuple:
            if len(args) > len(self.validation):
                raise SchemeError('Wrong number of arguments, expected ' \
                                  'at most ' + str(len(self.validation)) + \
                                  ', found ' + str(len(args)))
            min_args = len(filter(lambda x: type(x) != list, self.validation))
            if len(args) < min_args:
                raise SchemeError('Wrong number of arguments, expected ' \
                                  'at least ' + str(min_args) + ', found ' + \
                                  str(len(args)))
            for i in xrange(0, len(args)):
                val = self.validation[i]
                if type(val) == list:
                    val = val[0]
                if not val(args[i]):
                    raise SchemeError('Invalid argument type ' + str(args[i]))
        else:
            raise TypeError('Invalid validation parameter.')
        # execute primitive
        return self.proc(*args)


#################
#
# Type validation
#
#
is_infinite = (lambda n: n == float('infinity') or n == float('-infinity'))
is_integer = (lambda n: type(n) == int)
is_rational = (lambda n: type(n) == fractions.Fraction or is_integer(n))
is_real = (lambda n: type(n) == float or is_infinite(n) or is_rational(n))
is_complex = (lambda n: type(n) == complex or is_real(n))

is_boolean = (lambda n: type(n) == bool)
is_symbol = (lambda n: type(n) == str) # TODO
is_char = (lambda n: type(n) == str and len(n) == 1)
is_vector = (lambda n: type(n) == Vector)
is_null = (lambda n: is_pair(n) and n.car == None and n.cdr == None)
is_number = (lambda n: is_complex(n))
is_string = (lambda n: type(n) == str)
is_procedure = (lambda n: type(n) == Procedure or type(n) == Primitive)

is_expression = (lambda n: n != None)

############
#
# Exceptions
#
#
class SchemeError(Exception):
    pass


############
#
# Parser
#
#
REGULAR = 1
QUOTE1  = 2
QUOTE2  = 3
LIST    = 4
STRING  = 5
VECTOR  = 6

def parse(code):

    # split tokens
    code = re.sub("(\#?\()", lambda m: ' %s ' % m.group(1), code)
    code = code.replace(')', ' ) ')
    tokens = code.split()

    def parenthesis_stack(qt):
        def parent_stack(s):
            return s.count('(') - s.count(')')
        return sum(map(parent_stack, qt))

    # join quotes & strings
    new_tokens = []
    regular, quote_simple, string = 1, 2, 3
    parsing = regular
    temp = []
    for tk in tokens:
        if parsing == regular:
            if tk == "'" or tk == '#(':
                parsing = quote_simple
                temp = [tk]
            elif tk.startswith('"') and not tk.endswith('"'):
                parsing = string
                temp = [tk]
            else:
                new_tokens.append(tk)
        elif parsing == quote_simple:
            temp.append(tk)
            if parenthesis_stack(temp) == 0:
                parsing = regular
                if quote_simple:
                    new_tokens.append(''.join(temp[0:2]) + ' '.join(temp[2:]))
        elif parsing == string:
            temp.append(tk)
            if tk.endswith('"') and not tk.endswith('\\"'):
                parsing = regular
                new_tokens.append(' '.join(temp))

    tokens = new_tokens

    # check for parenthesis balance
    stack = 0
    for tk in tokens:
        if tk == '(' or tk == '#(': stack += 1
        elif tk == ')': stack -= 1
    if stack > 0:
        raise SchemeError(str(stack) + ' opening parenthesis in excess.')
    elif stack < 0:
        raise SchemeError(str(abs(stack)) + ' closing parenthesis in excess.')

    def lispify(tokens, list_type=List, i=0):
        lst = list_type()
        while i < len(tokens):
            if tokens[i] == '(':
                v, i = lispify(tokens, List, i+1)
                lst.append(v)
            elif tokens[i] == '#(':
                v, i = lispify(tokens, Vector, i+1)
                lst.append(v)
            elif tokens[i] == ')':
                if type(lst) == Vector:
                    lst.close()
                return lst, i
            else:
                lst.append(tokens[i])
            i += 1
        return lst, -1

    tokens.insert(0, 'begin')
    lists, i = lispify(tokens)

    return lists



##############
#
# Environment
# Manager
#
#
class Environment:

    def __init__(self, parameters=(), operands=(), env=None):
        self.data = {}
        self.upper_env = env
        if len(parameters) != len(operands):
            raise TypeError(str(len(parameters)) + \
                            ' arguments expected, found ' + str(len(operands)))
        for i in xrange(0, len(parameters)):
            self.create(parameters[i], operands[i])

    def get(self, key):
        try:
            return self.data[key]
        except KeyError:
            if self.upper_env == None:
                raise KeyError()
            else:
                return self.upper_env.get(key)

    def create(self, key, value):
        self.data[key] = value

    def set(self, key, value):
        if key in self.data:
            self.data[key] = value
        elif self.upper_env != None:
            self.upper_env.set(key, value)
        else:
            raise KeyError()

    def has_variable(self, key):
        if key in self.data:
            return True
        elif self.upper_env == None:
            return False
        else:
            return self.upper_env.has_variable(key)


############
#
# Evaluator
#
#
class SchemePy(object):

    def __init__(self):
        self.GE = Environment()
        self.add_primitives(self.GE)
        self.reserved_words = self.setup_reserved_words()


    def run(self, code):
        return self.eval(parse(code), self.GE)


    def eval(self, exp, env):
        # Self-evaluating expression
        val = self.eval_self_evaluating(exp)
        if val != None:
            return val

        # Variable
        elif type(exp) == str and env.has_variable(exp):
            return env.get(exp)

        # Reserved words
        elif type(exp) == List and exp.car in self.reserved_words:
            return self.reserved_words[exp.car](exp, env)

        # Procedures
        elif type(exp) == List:
            if exp.cdr == None:
                return self.apply(self.eval(exp.car, env), List())
            else:
                return self.apply(self.eval(exp.car, env), \
                                  map(lambda x: self.eval(x, env), exp.cdr))
        # Error
        else:
            raise SchemeError("Invalid expression " + str(exp))


    def eval_sequence(self, exp, env):
        v = None
        for e in exp:
            v = self.eval(e, env)
        return v


    def apply(self, operator, operands):
        if type(operator) == types.FunctionType:
            return apply(operator, operands) # this is python's apply!
        elif type(operator) == Primitive:
            return operator.apply(operands)
        elif type(operator) == Procedure:
            return self.eval_sequence(operator.body, \
                   Environment(operator.parameters, operands, operator.env))


    ##################
    #
    # Self-evaluating
    # expressions
    #
    #
    def eval_self_evaluating(self, exp):
        if type(exp) == str:

            # Boolean
            if exp == '#t':
                return True
            elif exp == '#f':
                return False

            # Caracter
            elif exp.startswith('#\\'):
                if exp[2:] == 'newline':
                    return '\n'
                elif exp[2:] == 'space':
                    return ' '
                elif len(exp) == 3:
                    return exp[2:]
                elif exp == '#\\':
                    return ' '
                else:
                    raise SchemeError('Invalid expression ' + exp)

            # Number
            elif re.match('^\#b\-?[01]+$', exp):
                if exp[2:3] == '-':
                    return eval('-0b' + exp[3:])
                else:
                    return eval('0b' + exp[2:])
            elif re.match('^\#o\-?[0-7]+$', exp):
                if exp[2:3] == '-':
                    return eval('-0' + exp[3:])
                else:
                    return eval('0' + exp[2:])
            elif re.match('^\#d\-?[0-9]+$', exp):
                if exp[2:3] == '-':
                    return eval('-' + exp[3:])
                else:
                    return eval(exp[2:])
            elif re.match('^\#x\-?[0-9A-Fa-f]+$', exp):
                if exp[2:3] == '-':
                    return eval('-0x' + exp[3:])
                else:
                    return eval('0x' + exp[2:])
            elif re.match('^\#i\-?[0-9\.]+$', exp):
                if exp[2:3] == '-':
                    return float(eval('-' + exp[3:]))
                else:
                    return float(eval(exp[2:]))
            elif re.match('^\#e\-?[0-9\.]+$', exp):
                if exp[2:3] == '-':
                    return int(eval('-' + exp[3:]))
                else:
                    return int(eval(exp[2:]))
            elif re.match('^\-?[0-9]+$', exp):
                return int(exp)
            elif re.match('^\-?[0-9]+?\.[0-9]+$', exp):
                return float(exp)
            elif re.match('^\-?[0-9]+\/[0-9]+$', exp):
                n = exp.split('/')
                return fractions.Fraction(int(n[0]), int(n[1]))
            elif re.match('^\-?[0-9\.]+(\+|\-)[0-9\.]+i$', exp):
                r = re.match('^(\-?[0-9\.]+)((\+|\-)[0-9\.]+)i$', exp).groups()
                return complex(float(r[0]), float(r[1]))

            # string
            elif exp.startswith('"') and exp.endswith('"'):
                return exp[1:len(exp)-1]

            # quotes
            elif exp.startswith('\''):
                return Datum(exp[1:])

            else:
                return None


        # vector
        elif type(exp) == Vector or type(exp) == Datum:
            return exp
        else:
            return None


    ##################
    #
    # Reserved words
    #
    #
    def setup_reserved_words(self):
        return {
            'define': self.eval_define,
            'set!':   self.eval_set,
            'lambda': self.eval_lambda,
            'begin':  self.eval_begin,
            'if':     self.eval_if,
            'cond':   self.eval_cond,
            'let':    self.eval_let,
            'let*':   self.eval_let_star,
        }

    def eval_define(self, exp, env):
        if type(exp[1]) == List:
            if env.has_variable(exp[1]):
                raise ValueError('Variable ' + exp[1] + ' already defined.')
            env.create(exp[1][0], Procedure(exp[1].cdr, exp.cdr.cdr, env))
        else:
            if env.has_variable(exp[1]):
                raise ValueError('Variable ' + exp[1] + ' already defined.')
            env.create(exp[1], self.eval(exp[2], env))
        return None

    def eval_set(self, exp, env):
        if not env.has_variable(exp[1]):
            raise ValueError('Variable ' + exp[1] + ' not found.')
        env.set(exp[1], self.eval(exp[2], env))
        return None

    def eval_lambda(self, exp, env):
        return Procedure(exp[1], exp.cdr.cdr, env)

    def eval_begin(self, exp, env):
        return self.eval_sequence(exp.cdr, env)

    def eval_if(self, exp, env):
        if self.eval(exp[1], env):
            return self.eval(exp[2], env)
        else:
            return self.eval(exp[3], env)

    def eval_cond(self, exp, env):
        i = 0
        for e in exp.cdr:
            if e[0] == 'else':
                if i != len(exp.cdr)-2:
                    return self.eval(e[1], env)
                else:
                    raise SchemeError("Misplaced else in cond")
            if self.eval(e[0], env):
                return self.eval(e[1], env)
            i += 1
        return None

    def eval_let(self, exp, env):
        parameters = []
        operands = []
        for e in exp[1]:
            parameters.append(e[0])
            operands.append(self.eval(e[1], env))
        p = Procedure(parameters, exp.cdr.cdr, env)
        return self.apply(p, operands)

    def eval_let_star(self, exp, env):
        current_env = env
        for e in exp[1]:
            current_env = Environment((e[0],), \
                                      (self.eval(e[1], current_env),), \
                                      current_env)
        p = Procedure(List(), exp.cdr.cdr, current_env)
        return self.apply(p, [])

    ##############
    #
    # Primitives
    #
    #
    def add_primitives(self, env):

        # Equivalence
        #
        env.create('eqv?', Primitive(
            lambda x,y: x.__hash__() == y.__hash__(),
            (is_expression, is_expression)))
        env.create('eq?', Primitive(
            lambda x,y: x.__hash__() == y.__hash__(),
            (is_expression, is_expression)))
        env.create('equal?', Primitive(
            lambda x,y: x == y,
            (is_expression, is_expression)))

        # Identification
        #
        env.create('number?', Primitive(is_number, (is_expression,)))
        env.create('complex?', Primitive(is_complex, (is_expression,)))
        env.create('real?', Primitive(is_real, (is_expression,)))
        env.create('rational?', Primitive(is_rational, (is_expression,)))
        env.create('integer?', Primitive(is_integer, (is_expression,)))
        env.create('exact?', Primitive(is_rational, (is_expression,)))
        env.create('inexact?', Primitive(
            lambda n: not is_rational(n),
            (is_expression,)))

        # Comparison
        #
        env.create('<', Primitive(
            lambda *args: check_all_true(operator.lt, args),
            is_number))
        env.create('>', Primitive(
            lambda *args: check_all_true(operator.gt, args),
            is_number))
        env.create('<=', Primitive(
            lambda *args: check_all_true(operator.le, args),
            is_number))
        env.create('>=', Primitive(
            lambda *args: check_all_true(operator.ge, args),
            is_number))
        env.create('=', Primitive(
            lambda *args: check_all_true(operator.eq, args),
            is_number))

        env.create('zero?', Primitive(
            lambda n: n == 0
            (is_number,)))
        
        # Numeric
        #
        env.create('+', Primitive(
            lambda *args: sum(args),
            is_number))
        env.create('-', Primitive(
            lambda *args: reduce(lambda x,y: x-y, args),
            is_number))
        env.create('*', Primitive(
            lambda *args: reduce(lambda x,y: x*y, args),
            is_number))

        # Pairs
        env.create('cons', Primitive(
            lambda x,y: List(x,y),
            (is_expression, is_expression)))


def check_all_true(op, lst):
    for i in xrange(0, len(lst)-1):
        if not apply(op, (lst[i], lst[i+1])):
            return False
    return True


if __name__ == '__main__':
    s = SchemePy()
